package com.jia.jianzhiOffer;
/**
 *面试题36： 二叉搜索树与双向链表
 * 题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * @author Administrator
 *
 */
public class Pro36 {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
    Node first = null;
    Node last = null;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        inorderTraveseConvertNode(root);
        //最后首尾连接
        last.right = first;
        first.left = last;
        return first;
    }
    private void inorderTraveseConvertNode(Node node) {
        if(node != null) {
            inorderTraveseConvertNode(node.left);
            if(last != null) {
                last.right = node;
                node.left = last;
            }else {
                first = node;
            }
            last = node;
            inorderTraveseConvertNode(node.right);
        }
    }
}
